﻿// 3823. 寻找字符串.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/3826/
给定一个由小写字母构成的字符串 s
。

请你找到一个满足如下所有要求的字符串 t
：

字符串 t
 是字符串 s
 的前缀。
字符串 t
 是字符串 s
 的后缀。
字符串 t
 在字符串 s
 的中间出现过。也就是作为一个既非前缀也非后缀的子串出现过。
字符串 t
 的长度应尽可能长。
输入格式
第一行包含整数 T
，表示共有 T
 组测试数据。

每组数据占一行，包含一个字符串 s
。

输出格式
每组数据输出一行结果，如果 t
 存在，则输出 t
，否则输出 not exist。

数据范围
前三个测试点满足 1≤|s|≤20
。
所有测试点满足 1≤T≤10
，1≤|s|≤106
。
同一测试点内所有输入字符串 s
 的长度之和不超过 106
。

输入样例：
2
fixprefixsuffix
abcdabc
输出样例：
fix
not exist
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 